import java.util.List;
import java.util.Arrays;
import java.util.Iterator;

/**
 * 
 * @author yangmqglobe
 *
 */
public class MGraph {
	public final static int INFINITY = Integer.MAX_VALUE;
	private GraphKind kind;
	private int vexNum, arcNum;
	private List<Object> vexs;
	private int[][] arcs;

	public MGraph(GraphKind kind, Object vexs[], int[][] arcs)
			throws ArrayIndexOutOfBoundsException {
		this.kind = kind;
		this.vexNum = vexs.length;
		this.arcNum = arcs.length;
		this.vexs = Arrays.asList(vexs);
		createGraph(arcs);
	}

	private void createGraph(int[][] arcs)
			throws ArrayIndexOutOfBoundsException {
		this.arcs = new int[vexNum][vexNum];
		switch (this.kind) {
		case UDG:
			createUDG(arcs);
			break;
		case DG:
			createDG(arcs);
			break;
		case UDN:
			createUDN(arcs);
			break;
		case DN:
			createDN(arcs);
			break;
		}
	}

	private void createUDG(int[][] arcs) throws ArrayIndexOutOfBoundsException {
		for (int[] arc : arcs) {
			int x = arc[0];
			int y = arc[1];
			this.arcs[x][y] = 1;
			this.arcs[y][x] = 1;
		}
	}

	private void createDG(int[][] arcs) throws ArrayIndexOutOfBoundsException {
		for (int[] arc : arcs) {
			int x = arc[0];
			int y = arc[1];
			this.arcs[x][y] = 1;
		}
	}

	private void fillArcs() {
		for (int i = 0; i < arcs.length; i++) {
			for (int j = 0; j < arcs[i].length; j++) {
				arcs[i][j] = INFINITY;
			}
		}
	}

	private void createUDN(int[][] arcs) throws ArrayIndexOutOfBoundsException {
		fillArcs();
		for (int[] arc : arcs) {
			int x = arc[0];
			int y = arc[1];
			int weight = arc[2];
			this.arcs[x][y] = weight;
			this.arcs[y][x] = weight;
		}
	}

	private void createDN(int[][] arcs) throws ArrayIndexOutOfBoundsException {
		fillArcs();
		for (int[] arc : arcs) {
			int x = arc[0];
			int y = arc[1];
			int weight = arc[2];
			this.arcs[x][y] = weight;
		}
	}

	public int locateVex(Object vex) {
		return vexs.indexOf(vex);
	}

	public int firstAdjVex(int v) throws Exception {
		if (v < 0 || v >= vexNum) {
			throw new Exception("Illegal argument!");
		}
		for (int i = 0; i < vexNum; i++) {
			if (arcs[v][i] != 0 && arcs[v][i] < INFINITY) {
				return i;
			}
		}
		return -1;
	}

	public int nextAdjVex(int v, int w) throws Exception {
		if (v < 0 || v >= vexNum && w > vexNum) {
			throw new Exception("Illegal argument!");
		}
		for (int i = w + 1; i < vexNum; i++) {
			if (arcs[v][i] != 0 && arcs[v][i] < INFINITY) {
				return i;
			}
		}
		return -1;
	}

	public Object getVex(int i) throws Exception {
		if (i < 0 && i >= vexNum) {
			throw new Exception("Illegal index!");
		}
		return vexs.get(i);
	}

	public GraphKind getKind() {
		return kind;
	}

	public int getVexNum() {
		return vexNum;
	}

	public int getArcNum() {
		return arcNum;
	}

	@Override
	public String toString() {
		String string = kind + "-MGraph@" + Integer.toHexString(hashCode());
		return string;
	}

	public String getString() {
		String string = " \t";
		for (Object obj : vexs) {
			string += obj.toString() + "\t";
		}
		string += "\n";
		for (int i = 0; i < arcs.length; i++) {
			string += vexs.get(i).toString() + "\t";
			for (int arc : arcs[i]) {
				if (arc == INFINITY) {
					string += "∞" + "\t";
				} else {
					string += arc + "\t";
				}
			}
			string += "\n";
		}
		return string;
	}
}
